package org.example.everyday;

import java.util.Map;
import java.util.TreeMap;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * <p>
 *
 * @author anlu
 * @date 2022/6/20 0020 21:43
 */
public class RangeModule{
    TreeMap<Integer, Integer> intervals;

    public static void main(String[] args) {
        RangeModule rangeModule = new RangeModule();
        rangeModule.intervals.put(11,20);
        rangeModule.intervals.put(12,21);
        rangeModule.intervals.put(4,5);
        rangeModule.intervals.put(1,2);

        rangeModule.addRange(10, 20);
        rangeModule.addRange(9, 21);
        rangeModule.addRange(8, 22);
        rangeModule.addRange(9, 19);
        rangeModule.addRange(10, 23);
        rangeModule.addRange(11, 20);
        rangeModule.removeRange(14, 16);
        //返回 true （区间 [10, 14) 中的每个数都正在被跟踪）
        rangeModule.queryRange(10, 14);
        //返回 false（未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字）
        rangeModule.queryRange(13, 15);
        //返回 true （尽管执行了删除操作，区间 [16, 17) 中的数字 16 仍然会被跟踪
        rangeModule.queryRange(16, 17);


    }

    public RangeModule() {
        intervals = new TreeMap<Integer, Integer>();
    }

    public void addRange(int left, int right) {
        Map.Entry<Integer, Integer> entry = intervals.higherEntry(left);
        if (entry != intervals.firstEntry()) {
            Map.Entry<Integer, Integer> start = entry != null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();
            if (start != null && start.getValue() >= right) {
                return;
            }
            if (start != null && start.getValue() >= left) {
                left = start.getKey();
                intervals.remove(start.getKey());
            }
        }
        while (entry != null && entry.getKey() <= right) {
            right = Math.max(right, entry.getValue());
            intervals.remove(entry.getKey());
            entry = intervals.higherEntry(entry.getKey());
        }
        intervals.put(left, right);
    }

    public boolean queryRange(int left, int right) {
        Map.Entry<Integer, Integer> entry = intervals.higherEntry(left);
        if (entry == intervals.firstEntry()) {
            return false;
        }
        entry = entry != null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();
        return entry != null && right <= entry.getValue();
    }


    public void removeRange(int left, int right) {
        Map.Entry<Integer,Integer> entry = intervals.higherEntry(left);
        if(entry != intervals.firstEntry()){
            Map.Entry<Integer,Integer> start = entry != null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();
            if(start != null && start.getValue() >= right){
                int ri = start.getValue();
                if(start.getKey() == left){
                    intervals.remove(start.getKey());
                } else {
                    intervals.put(start.getKey(),left);
                }
                if(right != ri){
                    intervals.put(right,ri);
                }
                return;
            }else if(start != null && start.getValue() > left){
                intervals.put(start.getKey(),left);
            }
        }
        while (entry != null && entry.getKey() < right){
            if(entry.getValue() <= right){
                intervals.remove(entry.getKey());
                entry = intervals.higherEntry(entry.getKey());
            }else {
                intervals.put(right,entry.getValue());
                intervals.remove(entry.getKey());
                break;
            }
        }
    }


}
